Limit Laws for Functions of Fringe trees for Binary Search Trees and Recursive Trees

摘要

We prove limit theorems for sums of functions of subtrees of binary searchtrees and random recursive trees. In particular, we give simple new proofs ofthe fact that the number of fringe trees of size $ k=k_n $ in the binary searchtree and the random recursive tree (of total size $ n $) asymptotically has aPoisson distribution if $ k\rightarrow\infty $, and that the distribution isasymptotically normal for $ k=o(\sqrt{n}) $. Furthermore, we prove similarresults for the number of subtrees of size $ k $ with some required property $P $, for example the number of copies of a certain fixed subtree $ T $. Usingthe Cram\'er-Wold device, we show also that these random numbers for differentfixed subtrees converge jointly to a multivariate normal distribution. As anapplication of the general results, we obtain a normal limit law for the numberof $\ell$-protected nodes in a binary search tree or random recursive tree. The proofs use a new version of a representation by Devroye, and Stein'smethod (for both normal and Poisson approximation) together with certaincouplings.